// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"cmd/compile/internal/ir"
	"cmd/compile/internal/types"
	"cmd/internal/src"
)

// dse在函数上执行死区存储消除。
// 死亡储备是指无条件遵循的储备
// 另一个存储到同一位置，没有中间负载。
// 此实现仅在基本块中工作。TODO:使用更全球化的东西。
func dse(f *Func) {
	var stores []*Value
	loadUse := f.newSparseSet(f.NumValues())
	defer f.retSparseSet(loadUse)
	storeUse := f.newSparseSet(f.NumValues())
	defer f.retSparseSet(storeUse)
	shadowed := f.newSparseMap(f.NumValues())
	defer f.retSparseMap(shadowed)
	for _, b := range f.Blocks {
		// 找到这个街区的所有商店。将其用途分类：
		// loadUse包含后续加载使用的存储。
		// storeUse包含由后续存储使用的存储。
		loadUse.clear()
		storeUse.clear()
		stores = stores[:0]
		for _, v := range b.Values {
			if v.Op == OpPhi {
				// 忽略网络钓鱼——它们永远是第一位的，无法消除
				continue
			}
			if v.Type.IsMemory() {
				stores = append(stores, v)
				for _, a := range v.Args {
					if a.Block == b && a.Type.IsMemory() {
						storeUse.add(a.ID)
						if v.Op != OpStore && v.Op != OpZero && v.Op != OpVarDef && v.Op != OpVarKill {
							// 电话、复印件等都是
							// 读和写。
							loadUse.add(a.ID)
						}
					}
				}
			} else {
				for _, a := range v.Args {
					if a.Block == b && a.Type.IsMemory() {
						loadUse.add(a.ID)
					}
				}
			}
		}
		if len(stores) == 0 {
			continue
		}

		// 找到街区的最后一家商店
		var last *Value
		for _, v := range stores {
			if storeUse.contains(v.ID) {
				continue
			}
			if last != nil {
				b.Fatalf("two final stores - simultaneous live stores %s %s", last.LongString(), v.LongString())
			}
			last = v
		}
		if last == nil {
			b.Fatalf("no last store found - cycle?")
		}

		// 向后走，寻找死掉的商店。跟踪隐藏的地址。
		// “隐藏地址”是一个指针和一个描述内存区域的大小
		// 这是众所周知的书面形式。我们跟踪隐藏地址中的隐藏地址
		// 映射，将地址的ID映射到阴影区域的大小。
		// 因为我们在向后走，所以对阴影区域的写入是无用的，
		// 因为它们将立即被覆盖。
		shadowed.clear()
		v := last

	walkloop:
		if loadUse.contains(v.ID) {
			// 可能有人正在读取此内存状态。
			// 清除所有隐藏的地址。
			shadowed.clear()
		}
		if v.Op == OpStore || v.Op == OpZero {
			var sz int64
			if v.Op == OpStore {
				sz = v.Aux.(*types.Type).Size()
			} else { // OpZero
				sz = v.AuxInt
			}
			if shadowedSize := int64(shadowed.get(v.Args[0].ID)); shadowedSize != -1 && shadowedSize >= sz {
				// 将store/zero修改为内存状态的副本，
				// 有效地避免了店铺运营。
				if v.Op == OpStore {
					// 存储地址值mem
					v.SetArgs1(v.Args[2])
				} else {
					// 零地址内存
					v.SetArgs1(v.Args[1])
				}
				v.Aux = nil
				v.AuxInt = 0
				v.Op = OpCopy
			} else {
				if sz > 0x7fffffff { // 解决sparseMap的int32值类型
					sz = 0x7fffffff
				}
				shadowed.set(v.Args[0].ID, int32(sz), src.NoXPos)
			}
		}
		// 步行到以前的商店
		if v.Op == OpPhi {
			// 在街区的起点。继续走到下一个街区。
			// 内存phi（如果存在）始终为
			// 块中的第一个逻辑存储。
			// （即使它不是当前b.值顺序中的第一个。）
			continue
		}
		for _, a := range v.Args {
			if a.Block == b && a.Type.IsMemory() {
				v = a
				goto walkloop
			}
		}
	}
}

// ElimReadAutoGeneric删除从未访问过的自动。要做到这一点,
// 我们跟踪每个自动的地址到达的操作，如果只有
// 到达门店，然后我们删除所有门店。然后，其他操作将继续
// 通过死代码消除通道消除。
func elimDeadAutosGeneric(f *Func) {
	addr := make(map[*Value]*ir.Name) // 自动进程地址达到的值
	elim := make(map[*Value]*ir.Name) // 如果自动关闭，则可以消除的值
	var used ir.NameSet               // 必须保留的二手车

	// 访问值并报告是否更新了任何地图
	visit := func(v *Value) (changed bool) {
		args := v.Args
		switch v.Op {
		case OpAddr, OpLocalAddr:
			// 如果地址指向自动，则传播该地址。
			n, ok := v.Aux.(*ir.Name)
			if !ok || n.Class != ir.PAUTO {
				return
			}
			if addr[v] == nil {
				addr[v] = n
				changed = true
			}
			return
		case OpVarDef, OpVarKill:
			// 如果我们取消自动变速器，v应该被取消。
			n, ok := v.Aux.(*ir.Name)
			if !ok || n.Class != ir.PAUTO {
				return
			}
			if elim[v] == nil {
				elim[v] = n
				changed = true
			}
			return
		case OpVarLive:
			// 如果汽车需要保持活动状态，请不要删除它。

			// 我们依靠此检查来保留autotmp堆栈插槽
			// 用于删除开放编码延迟（因为
			// 不能由内联代码使用，但将由
			// 恐慌处理）。
			n, ok := v.Aux.(*ir.Name)
			if !ok || n.Class != ir.PAUTO {
				return
			}
			if !used.Has(n) {
				used.Add(n)
				changed = true
			}
			return
		case OpStore, OpMove, OpZero:
			// 如果我们取消自动变速器，v应该被取消。
			n, ok := addr[args[0]]
			if ok && elim[v] == nil {
				elim[v] = n
				changed = true
			}
			// 其他参数可能包含指向自动的指针。
			args = args[1:]
		}

		// 下面的代码假设我们已经处理了所有的ops
		// 已经有sym效果了。检查一下这里。
		// 忽略参数，因为它们不能是自动的。
		if v.Op.SymEffect() != SymNone && v.Op != OpArg {
			panic("unhandled op with sym effect")
		}

		if v.Uses == 0 && v.Op != OpNilCheck && !v.Op.IsCall() && !v.Op.HasSideEffects() || len(args) == 0 {
			// 零支票没有用，但我们需要保留它。
			// 还保留有副作用的调用和值。
			return
		}

		// 如果auto的地址到达内存或控件
		// 以上未涉及的操作，我们可能需要保留它。
		// 如果汽车到达潜在危险装置，我们还需要保留它们（第26153号问题）。
		if v.Type.IsMemory() || v.Type.IsFlags() || v.Op == OpPhi || v.MemoryArg() != nil {
			for _, a := range args {
				if n, ok := addr[a]; ok {
					if !used.Has(n) {
						used.Add(n)
						changed = true
					}
				}
			}
			return
		}

		// 通过v传播任何自动地址。
		var node *ir.Name
		for _, a := range args {
			if n, ok := addr[a]; ok && !used.Has(n) {
				if node == nil {
					node = n
				} else if node != n {
					// 大多数时候，我们只看到一个指针
					// 达成行动，但有些行动可能需要
					// 多个指针（如NeqPtr、Phi等）。
					// 这是罕见的，所以只需传播第一个
					// 保持事物简单的价值。
					used.Add(n)
					changed = true
				}
			}
		}
		if node == nil {
			return
		}
		if addr[v] == nil {
			// 汽车的地址到达此op。
			addr[v] = node
			changed = true
			return
		}
		if addr[v] != node {
			// 这种情况在实践中不会发生，但要抓住它以防万一。
			used.Add(node)
			changed = true
		}
		return
	}

	iterations := 0
	for {
		if iterations == 4 {
			// 放弃
			return
		}
		iterations++
		changed := false
		for _, b := range f.Blocks {
			for _, v := range b.Values {
				changed = visit(v) || changed
			}
			// 如果其地址达到控制值，则保持自动
			for _, c := range b.ControlValues() {
				if n, ok := addr[c]; ok && !used.Has(n) {
					used.Add(n)
					changed = true
				}
			}
		}
		if !changed {
			break
		}
	}

	// 消除对未读汽车的存储。
	for v, n := range elim {
		if used.Has(n) {
			continue
		}
		// 替换为OpCopy
		v.SetArgs1(v.MemoryArg())
		v.Aux = nil
		v.AuxInt = 0
		v.Op = OpCopy
	}
}

// elimUnreadAutos删除存储（以及相关的簿记操作VarDef和VarKill）
// 到从未从中读取的汽车。
func elimUnreadAutos(f *Func) {
	// 对影响汽车的所有操作进行循环，注意
	// 我们需要的汽车，以及我们可能需要的存储
	// 排除
	var seen ir.NameSet
	var stores []*Value
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			n, ok := v.Aux.(*ir.Name)
			if !ok {
				continue
			}
			if n.Class != ir.PAUTO {
				continue
			}

			effect := v.Op.SymEffect()
			switch effect {
			case SymNone, SymWrite:
				// 如果我们还没有看到汽车
				// 那么这可能是一家我们可以去的商店
				// 排除
				if !seen.Has(n) {
					stores = append(stores, v)
				}
			default:
				// 假设需要自动变速器（已加载，
				// 其地址已被占用等）。
				// 注：我们必须检查其用途
				// 因为死荷载还没有被移除
				// 还没有被淘汰。
				if v.Uses > 0 {
					seen.Add(n)
				}
			}
		}
	}

	// 消除对未读汽车的存储。
	for _, store := range stores {
		n, _ := store.Aux.(*ir.Name)
		if seen.Has(n) {
			continue
		}

		// 用OpCopy替换存储
		store.SetArgs1(store.MemoryArg())
		store.Aux = nil
		store.AuxInt = 0
		store.Op = OpCopy
	}
}
